package com.shiguiwu.springmybatis.algorithm.sort;

import java.util.Arrays;

/**
 * @description: 归并排序
 * 分-治思想
 * @author: stone
 * @date: Created by 2021/3/27 11:26
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.sort
 */
public class MergeSort extends AbstractSort  implements Sort{

    public static void main1(String[] args) {
        int[] tests =SortTests.init(10);
//        int[] temp = new int[tests.length];
//        merge(tests, 0, 2, 5, temp);
        MergeSort sort = new MergeSort(tests);
        sort.sort();
        System.out.println(Arrays.toString(tests));

    }

    public MergeSort(int[] array) {
        super(array);
    }

    @Override
    public void sort() {
        int[] temp = new int[array.length];
        this.mergeSort(array, 0, array.length - 1, temp);

    }

    /**
     * 分+治
     * @param array 带排序数组
     * @param left 左边
     * @param right 右边的数
     * @param temp 临时数组
     */
    private void mergeSort(int[] array, int left, int right, int[] temp) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        //向左递归
        mergeSort(array, left, mid, temp);
        //向右递归
        mergeSort(array, mid + 1, right, temp);
        //合并，利用栈的机制，重最后执行的方法开始
        merge(array, left, mid, right, temp);

    }


    /**
     * 合，才是重点，需要做三件事情
     * @param array 待排序的数组
     * @param left 最左边的数
     * @param mid 中间的数
     * @param right 右边的数
     * @param temp 临时数组，用于排序
     */
    private  void merge(int[] array, int left, int mid, int right,int[] temp) {
        //1，比较左边量表的数，谁小，谁先放在temp
//        System.out.println("在合并中。。。。。。。。。。。");
        int i = left;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[index] = array[i];
                i++;
                index++;
            }
            else {
                temp[index] = array[j];
                j++;
                index++;
            }
        }

        //2，把剩余的数据，一并放入的temp中，因为比完后，两边都有可能剩余
        while (i <= mid) {
            temp[index] = array[i];
            i++;
            index++;

        }

        while (j <= right) {
            temp[index] = array[j];
            j++;
            index++;

        }
        //3，临时数组拷贝到目标数组中 && right == array.length-1 && left == 0
        int left1 = left;
        index = 0;
        while (left1 <= right) {
            array[left1] = temp[index];
            left1++;
            index++;
        }
    }
}
